<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8">
        <title>迷宫游戏</title>
        <script src="https://cdn.bootcdn.net/ajax/libs/jquery/3.6.0/jquery.min.js"></script>
        <style>
            * {
                margin: 0;
                padding: 0;
            }

            .maze-outer-wrapper {
                display: flex;
                margin-left: 20%;
                margin-top: 10px;
                align-items: center;
            }

            .maze-outer {
                height: 700px;
                width: 700px;
                border: 1px solid black;
            }

            .first-grid {
                width: 100%;
                height: 70px;
                display: flex;
            }

            .second-grid {
                width: 70px;
                height: 100%;
                background-color: gold;
                border-right: 1px solid black;
                border-bottom: 1px solid black;
                box-sizing: border-box;
                display: flex;
                align-items: center;
                justify-content: space-around;
                font-size: 12px;
            }

            .first-grid:last-child .second-grid {
                border-bottom: none;
            }

            .second-grid:last-child {
                border-right: none;
            }

            .none-right {
                border-right: none;
            }

            .none-bottom {
                border-bottom: none;
            }

            .wolfman {
                background-color: red;
            }

            .operator {
                width: 100px;
                margin-left: 100px;
                text-align: center;
            }

            .maze-generate-wrapper div, .automatic-way-finding div, .game-help div {
                height: 25px;
                width: 100%;
                background-color: greenyellow;
                margin-top: 15px;
                cursor: pointer;
                border-radius: 3px;
            }

            .maze-generate-wrapper div:first-child, .automatic-way-finding div:first-child, .game-help div:first-child {
                cursor: default;
                background-color: teal;
            }

            .maze-generate-wrapper {
            }

            .automatic-way-finding {
                margin-top: 45px;
            }

            .game-help {
                margin-top: 45px;
            }

            .message {
                font-size: 20px;
                text-align: center;
                height: 18px;
                margin-bottom: 25px;
            }
        </style>
    </head>
    <body>
        <div class="maze-outer-wrapper">
            <div class="maze-outer">
                <div class="first-grid">
                    <div class="second-grid wolfman"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                </div>
                <div class="first-grid">
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                </div>
                <div class="first-grid">
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                </div>
                <div class="first-grid">
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                </div>
                <div class="first-grid">
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                    <div class="second-grid"></div>
                </div>
            </div>
            <div class="operator">
                <div class="message"></div>
                <div class="maze-generate-wrapper">
                    <div>迷宫生成</div>
                    <div class="recursive-backtracking">递归回溯</div>
                    <div class="random-prim">随机prim</div>
                    <div class="region-segmentation">区域分割</div>
                </div>
                <div class="automatic-way-finding">
                    <div>自动寻路</div>
                    <div class="depth-first">深度优先</div>
                    <div class="breadth-first">广度优先</div>
                </div>
                <div class="game-help">
                    <div>游戏选项</div>
                    <div class="restart-game">重新开始</div>
                    <div class="to-up">上</div>
                    <div class="to-down">下</div>
                    <div class="to-left">左</div>
                    <div class="to-right">右</div>
                </div>
            </div>
        </div>
        <script>
            //迷宫墙壁
            let mazeOuter = $(".maze-outer");
            //消息提示
            let message = $(".message");
            //迷宫
            let maze = [];
            //迷宫格子数
            let n = 10;
            //当前人物位置
            let x = 0;
            let y = 0;
            //是否正在自动寻路
            let isAutoFind = false;
            //定时器
            let timer;
            //深度遍历是否找到最终点
            let dfsFindPathFlag = false;


            //判断是否还有剩余单元格未访问
            function isAllVisited(maze) {
                for (let i = 0; i < n; i++) {
                    for (let j = 0; j < n; j++) {
                        if (!maze[i][j].visited) {
                            return true;
                        }
                    }
                }
                return false;
            }

            //获取随机元素
            function getRandomGrid(unVisited) {
                let index = Math.floor(Math.random() * unVisited.length);
                return unVisited[index];
            }

            //移除两个格子间的墙壁
            function removeWall(cur, nei) {
                //nei在cur的上部
                if (cur.i - 1 >= 0 && cur.i - 1 === nei.i && cur.j === nei.j) {
                    nei.class += " none-bottom";
                }
                //nei在cur的右部
                if (cur.j + 1 < n && cur.j + 1 === nei.j && cur.i === nei.i) {
                    cur.class += " none-right";
                }
                //nei在cur的下部
                if (cur.i + 1 < n && cur.i + 1 === nei.i && cur.j === nei.j) {
                    cur.class += " none-bottom";

                }
                //nei在cur的左部
                if (cur.j - 1 >= 0 && cur.j - 1 === nei.j && cur.i === nei.i) {
                    nei.class += " none-right";
                }
            }

            ///绘制迷宫
            function drawMaze(maze) {
                let m = '';
                for (let i = 0; i < maze.length; i++) {
                    let firstGrid = '<div class="first-grid">';
                    for (let j = 0; j < maze[0].length; j++) {
                        firstGrid += `<div class="${maze[i][j].class.trim()}"></div>`;
                    }
                    firstGrid += '</div>';
                    m += firstGrid;
                }
                mazeOuter.html(m);
            }

            //改变人物位置
            function changeCubePosition(i, j) {
                if (i < 0 || j < 0 || i >= n || j >= n) {
                    return;
                }
                let firstChildren = mazeOuter.children();
                //添加新的标记
                $($(firstChildren[i]).children()[j]).addClass("wolfman");
                // $($(firstChildren[i]).children()[j]).text(maze[i][j].layer);
                if (i === n - 1 && j === n - 1) {
                    message.text("游戏成功");
                    message.fadeIn();
                }
            }

            //广度搜索自动寻路
            function getShortestPathBFS(start, end) {
                let queue = [];
                let path = [];
                for (let i = 0; i < n; i++) {
                    for (let j = 0; j < n; j++) {
                        maze[i][j].visited = false;
                    }
                }
                let layer = 1;
                maze[start][end].layer = layer++;
                queue.push(maze[start][end]);
                path.push(maze[start][end]);
                while (queue.length !== 0) {
                    for (let i = queue.length; i > 0; i--) {
                        let q = queue.shift();
                        path.push(q);
                        q.visited = true;
                        //上
                        if (q.i - 1 >= 0 && !maze[q.i - 1][q.j].visited && getCubePosition(q.i - 1, q.j).className.indexOf("none-bottom") > 0) {
                            maze[q.i - 1][q.j].layer = layer;
                            queue.push(maze[q.i - 1][q.j]);
                        }
                        //右
                        if (q.j + 1 < n && !maze[q.i][q.j + 1].visited && getCubePosition(q.i, q.j).className.indexOf("none-right") > 0) {
                            maze[q.i][q.j + 1].layer = layer;
                            queue.push(maze[q.i][q.j + 1]);
                        }
                        //下
                        if (q.i + 1 < n && !maze[q.i + 1][q.j].visited && getCubePosition(q.i, q.j).className.indexOf("none-bottom") > 0) {
                            maze[q.i + 1][q.j].layer = layer;
                            queue.push(maze[q.i + 1][q.j]);
                        }
                        //左
                        if (q.j - 1 >= 0 && !maze[q.i][q.j - 1].visited && getCubePosition(q.i, q.j - 1).className.indexOf("none-right") > 0) {
                            maze[q.i][q.j - 1].layer = layer;
                            queue.push(maze[q.i][q.j - 1]);
                        }
                    }
                    layer++;
                }
                let s = 0;
                path = getShortestPath(path);
                // removeCubePosition(x, y);
                x = path[s].i;
                y = path[s].j;
                changeCubePosition(x, y);
                timer = setInterval(function () {
                    if (s >= path.length || (path[s].i === n - 1 && path[s].j === n - 1)) {
                        clearInterval(timer);
                        return;
                    }
                    s++;
                    // removeCubePosition(x, y);
                    if (s >= path.length) {
                        clearInterval(timer);
                        return;
                    }
                    x = path[s].i;
                    y = path[s].j;
                    changeCubePosition(x, y);
                }, 50);

            }

            //根据广度搜索结果集获取最短路径
            function getShortestPath(path) {
                let result = [];
                result.push(maze[n - 1][n - 1]);
                for (let i = path.length - 2; i >= 0; i--) {
                    let cur = result[0];
                    let nei = path[i];
                    if (reachable(cur, nei) && cur.layer > nei.layer) {
                        result.unshift(nei);
                    }
                }
                return result;
            }

            //判断cur和nei是否互通
            function reachable(cur, nei) {
                //nei在cur的上部
                if (cur.i - 1 >= 0 && cur.i - 1 === nei.i && cur.j === nei.j) {
                    return nei.class.indexOf("none-bottom") >= 0;
                }
                //nei在cur的右部
                if (cur.j + 1 < n && cur.j + 1 === nei.j && cur.i === nei.i) {
                    return cur.class.indexOf("none-right") >= 0;

                }
                //nei在cur的下部
                if (cur.i + 1 < n && cur.i + 1 === nei.i && cur.j === nei.j) {
                    return cur.class.indexOf("none-bottom") >= 0;
                }
                //nei在cur的左部
                if (cur.j - 1 >= 0 && cur.j - 1 === nei.j && cur.i === nei.i) {
                    return nei.class.indexOf("none-right") >= 0;
                }
                return false;
            }


            //深度搜索自动寻路
            function dfs(start, path) {
                if (start.i < 0 || start.j < 0 || start.i >= n || start.j >= n || dfsFindPathFlag) {
                    return;
                }
                start.visited = true;
                path.push(start);
                if (start.i === n - 1 && start.j === n - 1) {
                    dfsFindPathFlag = true;
                    return;
                }
                //上
                if (start.i - 1 >= 0 && !maze[start.i - 1][start.j].visited && getCubePosition(start.i - 1, start.j).className.indexOf("none-bottom") > 0) {
                    dfs(maze[start.i - 1][start.j], path);
                }
                //右
                if (start.j + 1 < n && !maze[start.i][start.j + 1].visited && getCubePosition(start.i, start.j).className.indexOf("none-right") > 0) {
                    dfs(maze[start.i][start.j + 1], path);
                }
                //下
                if (start.i + 1 < n && !maze[start.i + 1][start.j].visited && getCubePosition(start.i, start.j).className.indexOf("none-bottom") > 0) {
                    dfs(maze[start.i + 1][start.j], path);
                }
                //左
                if (start.j - 1 >= 0 && !maze[start.i][start.j - 1].visited && getCubePosition(start.i, start.j - 1).className.indexOf("none-right") > 0) {
                    dfs(maze[start.i][start.j - 1], path);
                }
                if (path.length !== 0 && !dfsFindPathFlag) {
                    path.pop();
                }
            }

            //深度搜索自动寻路
            function getShortestPathDFS(start, end) {
                let path = [];
                for (let i = 0; i < n; i++) {
                    for (let j = 0; j < n; j++) {
                        maze[i][j].visited = false;
                    }
                }
                dfs(maze[start][end], path);
                let s = 0;
                // removeCubePosition(x, y);
                x = path[s].i;
                y = path[s].j;
                changeCubePosition(x, y);
                timer = setInterval(function () {
                    if (s === path.length || (path[s].i === n - 1 && path[s].j === n - 1)) {
                        clearInterval(timer);
                        return;
                    }
                    s++;
                    // removeCubePosition(x, y);
                    x = path[s].i;
                    y = path[s].j;
                    changeCubePosition(x, y);
                }, 50);
            }

            //删除指定位置人物轨迹
            function removeCubePosition(i, j) {
                if (i < 0 || j < 0 || i >= n || j >= n) {
                    return;
                }
                let firstChildren = mazeOuter.children();
                //将原来的标记删除
                $($(firstChildren[x]).children()[y]).removeClass("wolfman");
            }

            //根据i,j获取元素
            function getCubePosition(i, j) {
                if (i < 0 || j < 0 || i >= n || j >= n) {
                    return;
                }
                let firstChildren = mazeOuter.children();
                let secondChildren = $(firstChildren[i]).children();
                return secondChildren[j];
            }

            //随机prism初始化迷宫
            function initMazeByRandomPrim() {
                // 1.让迷宫全是墙.
                // 2.选一个单元格作为迷宫的通路，然后把它的邻墙放入列表
                // 3.当列表里还有墙时
                //      1.从列表里随机选一个墙，如果这面墙分隔的两个单元格只有一个单元格被访问过
                //          1.那就从列表里移除这面墙，即把墙打通，让未访问的单元格成为迷宫的通路
                //          2.把这个格子的墙加入列表
                // 2.如果墙两面的单元格都已经被访问过，那就从列表里移除这面墙
                //
                // 解释一下就是：我们可以维护一个迷宫单元格的列表，而不是边的列表。在这个迷宫单元格列表里面存放了未访问的单元格，
                // 我们在单元格列表中随机挑选一个单元格，如果这个单元格有多面墙联系着已存在的迷宫通路，我们就随机选择一面墙打通。
                // 这会比基于边的版本分支稍微多一点。
                //初始化数组
                initMazeArray();
                //初始化墙
                let list = [];
                maze[0][0].visited = true;
                addWallToList(list, maze[0][0]);
                while (list.length !== 0) {
                    let index = Math.floor(Math.random() * list.length);
                    let w = list[index];
                    if (w.type === "right" && w.j + 1 < n) {
                        if ((maze[w.i][w.j].visited ^ maze[w.i][w.j + 1].visited)) {
                            maze[w.i][w.j + 1].visited = true;
                            maze[w.i][w.j].class += " none-right";
                            addWallToList(list, maze[w.i][w.j + 1]);
                        } else if (maze[w.i][w.j].visited && maze[w.i][w.j + 1].visited) {
                            list.splice(index, 1);
                        }

                    } else if (w.type === "bottom" && w.i + 1 < n) {
                        if ((maze[w.i][w.j].visited ^ maze[w.i + 1][w.j].visited)) {
                            maze[w.i + 1][w.j].visited = true;
                            maze[w.i][w.j].class += " none-bottom";
                            addWallToList(list, maze[w.i + 1][w.j]);
                        } else if (maze[w.i][w.j].visited && maze[w.i + 1][w.j].visited) {
                            list.splice(index, 1);
                        }
                    }
                }
            }

            function removeLeftOrRight(target) {
                if (target.j === n - 1) {
                    maze[target.i][target.j - 1].class += " none-right";
                } else {
                    target.class += " none-right";
                }
            }

            function removeUpOrDown(target) {
                if (target.i === n - 1) {
                    maze[target.i - 1][target.j].class += " none-bottom";
                } else {
                    target.class += " none-bottom";
                }
            }

            function getRandom(n, m) {
                return Math.floor(Math.random() * (m - n) + n + 0.5);
            }

            function drawLine(xStart, xEnd, yStart, yEnd, row, col) {
                //上
                let r1 = getRandom(xStart, row);
                //右
                let r2 = getRandom(col + 1, yEnd);
                //下
                let r3 = getRandom(row + 1, xEnd);
                //左
                let r4 = getRandom(yStart, col);
                for (let i = xStart; i < xEnd + 2; i++) {
                    for (let j = yStart; j < yEnd + 2; j++) {
                        if (i === row && j !== r2 && j !== r4) {
                            maze[i][j].class = maze[i][j].class.replace(/none-bottom/, "");
                        }
                        if (j === col && i !== r1 && i !== r3) {
                            maze[i][j].class = maze[i][j].class.replace(/none-right/, "1");
                        }
                    }
                }
            }

            function initMazeByRecursion(xStart, xEnd, yStart, yEnd) {
                if (xStart >= xEnd || yStart >= yEnd) {
                    return;
                }
                let row = getRandom(xStart, xEnd);
                let col = getRandom(yStart, yEnd);
                drawLine(xStart, xEnd, yStart, yEnd, row, col);
                //左上
                initMazeByRecursion(xStart, row - 1, yStart, col - 1);
                //右上
                initMazeByRecursion(xStart, row - 1, col + 1, yEnd);
                //右下
                initMazeByRecursion(row + 1, xEnd, col + 1, yEnd);
                //左下
                initMazeByRecursion(row + 1, xEnd, yStart, col - 1);
            }

            //基于分治法初始化迷宫
            function initMazeByDivideAndConquer() {
                //初始化数组
                initMazeArrayInDivideAndConquer();
                //递归生成迷宫
                initMazeByRecursion(0, n - 2, 0, n - 2);
            }

            function initMazeArrayInDivideAndConquer() {
                let temp = [];
                for (let i = 0; i < n; i++) {
                    let m = [];
                    for (let j = 0; j < n; j++) {
                        let item = {class: "second-grid none-right none-bottom", visited: false, i: i, j: j};
                        m.push(item);
                    }
                    temp.push(m);
                }
                maze = temp;
            }

            function addWallToList(list, grid) {
                if (grid.i === n - 1 && grid.j === n - 1) {
                } else if (grid.i === n - 1) {
                    list.push({i: grid.i, j: grid.j, type: "right"});
                } else if (grid.j === n - 1) {
                    list.push({i: grid.i, j: grid.j, type: "bottom"});
                } else {
                    list.push({i: grid.i, j: grid.j, type: "right"});
                    list.push({i: grid.i, j: grid.j, type: "bottom"});
                }
            }

            //初始化数组
            function initMazeArray() {
                let temp = [];
                for (let i = 0; i < n; i++) {
                    let m = [];
                    for (let j = 0; j < n; j++) {
                        let item = {class: "second-grid", visited: false, i: i, j: j};
                        m.push(item);
                    }
                    temp.push(m);
                }
                maze = temp;
            }

            //深度遍历初始化迷宫
            function initMazeByDfs() {
                // 1.将起点作为当前迷宫单元并标记为已访问
                // 2.当还存在未标记的迷宫单元，进行循环
                //      1.如果当前迷宫单元有未被访问过的的相邻的迷宫单元
                //          1.随机选择一个未访问的相邻迷宫单元
                //          2.将当前迷宫单元入栈
                //          3.移除当前迷宫单元与相邻迷宫单元的墙
                //          4.标记相邻迷宫单元并用它作为当前迷宫单元
                //      2.如果当前迷宫单元不存在未访问的相邻迷宫单元，并且栈不空
                //          1.栈顶的迷宫单元出栈
                //          2.令其成为当前迷宫单元
                let stack = [];
                //初始化数组
                initMazeArray();
                maze[0][0].visited = true;
                let i = 0, j = 0;
                //初始化迷宫
                while (isAllVisited(maze)) {
                    let unVisited = [];
                    //判断上一个单元格
                    if (i - 1 >= 0 && maze[i - 1][j].visited === false) {
                        unVisited.push(maze[i - 1][j]);
                    }
                    //判断右一个单元格
                    if (j + 1 < n && maze[i][j + 1].visited === false) {
                        unVisited.push(maze[i][j + 1]);
                    }
                    //判断下一个单元格
                    if (i + 1 < n && maze[i + 1][j].visited === false) {
                        unVisited.push(maze[i + 1][j]);
                    }
                    //判断左一个单元格
                    if (j - 1 >= 0 && maze[i][j - 1].visited === false) {
                        unVisited.push(maze[i][j - 1]);
                    }
                    if (unVisited.length !== 0) {
                        let r = getRandomGrid(unVisited);
                        r.visited = true;
                        stack.push(maze[i][j]);
                        removeWall(maze[i][j], r);
                        i = r.i;
                        j = r.j;
                    } else if (stack.length !== 0) {
                        let r = stack.pop();
                        i = r.i;
                        j = r.j;
                    }
                }
            }


            //初始化迷宫
            function initMaze() {
                //初始化迷宫
                //深度遍历
                // initMazeByDfs();
                //随机prim算法
                initMazeByRandomPrim();
                //分治法
                // initMazeByDivideAndConquer();
                //绘制迷宫
                drawMaze(maze);
                //初始化人物方块
                x = 0;
                y = 0;
                changeCubePosition(x, y);
            }

            //监听键盘事件
            function listenKeyDown(event) {
                let type = event.originalEvent.code;
                switch (type) {
                    case "KeyW":
                    case "ArrowUp":
                        toUp();
                        break;
                    case "KeyD":
                    case "ArrowRight":
                        toRight();
                        break;
                    case "KeyS":
                    case "ArrowDown":
                        toDown();
                        break;
                    case "KeyA":
                    case "ArrowLeft":
                        toLeft();
                        break;
                    default:
                        break;
                }
            }

            function recursiveBacktracking() {
                if (isAutoFind) {
                    return;
                }
                initMazeByDfs();
                //绘制迷宫
                drawMaze(maze);
                //初始化人物方块
                x = 0;
                y = 0;
                changeCubePosition(x, y);
            }

            function randomPrim() {
                if (isAutoFind) {
                    return;
                }
                //随机prim算法
                initMazeByRandomPrim();
                //绘制迷宫
                drawMaze(maze);
                //初始化人物方块
                x = 0;
                y = 0;
                changeCubePosition(x, y);
            }

            function regionSegmentation() {
                if (isAutoFind) {
                    return;
                }
                initMazeByDivideAndConquer();
                //绘制迷宫
                drawMaze(maze);
                //初始化人物方块
                x = 0;
                y = 0;
                changeCubePosition(x, y);
            }

            function restartGame() {
                //绘制迷宫
                drawMaze(maze);
                isAutoFind = false;
                message.text("");
                dfsFindPathFlag = false;
                clearInterval(timer);
                //初始化人物方块
                x = 0;
                y = 0;
                changeCubePosition(x, y);
            }

            function depthFirst() {
                if (isAutoFind) {
                    return;
                }
                isAutoFind = true;
                //自动寻路
                getShortestPathDFS(x, y);
            }

            function breadthFirst() {
                if (isAutoFind) {
                    return;
                }
                isAutoFind = true;
                //自动寻路
                getShortestPathBFS(x, y);
            }


            function toUp() {
                if (isAutoFind) {
                    return;
                }
                if (x - 1 >= 0 && getCubePosition(x - 1, y).className.indexOf("none-bottom") > 0) {
                    removeCubePosition(x, y);
                    changeCubePosition(--x, y);
                }
            }

            function toDown() {
                if (isAutoFind) {
                    return;
                }
                if (x + 1 < n && getCubePosition(x, y).className.indexOf("none-bottom") > 0) {
                    removeCubePosition(x, y);
                    changeCubePosition(++x, y);
                }
            }

            function toLeft() {
                if (isAutoFind) {
                    return;
                }
                if (y - 1 >= 0 && getCubePosition(x, y - 1).className.indexOf("none-right") > 0) {
                    removeCubePosition(x, y);
                    changeCubePosition(x, --y);
                }
            }

            function toRight() {
                if (isAutoFind) {
                    return;
                }
                if (y + 1 < n && getCubePosition(x, y).className.indexOf("none-right") > 0) {
                    removeCubePosition(x, y);
                    changeCubePosition(x, ++y);
                }
            }

            function initMazeGame() {
                //初始化迷宫
                initMaze();
                //绑定键盘监听事件
                $(window).bind('keydown', listenKeyDown);
                $(".recursive-backtracking").click(recursiveBacktracking);
                $(".random-prim").click(randomPrim);
                $(".region-segmentation").click(regionSegmentation);
                $(".restart-game").click(restartGame);
                $(".depth-first").click(depthFirst);
                $(".breadth-first").click(breadthFirst);
                $(".to-up").click(toUp);
                $(".to-down").click(toDown);
                $(".to-left").click(toLeft);
                $(".to-right").click(toRight);
            }


            $(function () {
                initMazeGame()
            });


        </script>
    </body>

</html>
